package com.dev.tools.sort;

import com.dev.tools.util.ArraysUtil;
import com.dev.tools.util.ReflectionUtil;
import java.util.*;

/**
 * @ClassName : Example1  //类名
 * @Description : 冒泡  //描述
 * @Author :   //作者
 */
public class Example1 {

    /**
     * 冒泡
     *  0 ~ n - 1
     *  0 ~ n - 2
     *  0 ~ n - 3
     */
    public static void bubbleSort(int[] list){
        if (isEmpty(list)){
            return;
        }
        //若上次循环没有交换数组元素，证明数组已为有序
        boolean isDisorder = true;
        for (int i = list.length - 1; i > 0 && isDisorder; i--) {
            isDisorder = false;
            for (int j = 0; j < i; j++) {
                if (list[j] > list[j + 1]) {
                    ArraysUtil.swap(list, j, j + 1);
                    isDisorder = true;
                }
            }
        }
    }

    /**
     * 插入
     * 依次保证0 ~ i - 1范围内有序
     * 依次保证1 ~ i - 1范围内有序
     * 依次保证2 ~ i - 1范围内有序
     */
    public static void insertionSort(int[] list){
        if (isEmpty(list)){
            return;
        }
        for (int i = 1; i < list.length; i++) {
            //0 ~ i - 1范围内有序
            for (int j = i - 1; j >= 0 && list[j] > list[j + 1]; j--) {
                ArraysUtil.swap(list, j, j + 1);
            }
        }
    }

    /**
     * 选择
     * 0 ~ n - 1位置最小值放到0
     * 1 ~ n - 1位置最小值放到1
     * 2 ~ n - 1位置最小值放到2
     */
    public static void selectionSort(int[] arr) {
        if (isEmpty(arr)){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            //0 ~ i位置最小值
            for (int j = i + 1; j < arr.length; j++) {
                min = arr[j] < arr[min] ? j : min;
            }
            if (i != min){
                ArraysUtil.swap(arr, i, min);
            }
        }
    }

    /**
     * 希尔
     */
    public static void hillSort(int[] arr) {
        if (isEmpty(arr)){
            return;
        }
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j - i; k >= 0; k -= i) {
                    if (arr[k + i] < arr[k]) {
                        ArraysUtil.swap(arr, k + i, k);
                    } else {
                        break;
                    }
                }
            }
        }
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (isEmpty(arr)){
            return;
        }
        if (l == r){
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int mid, int r){
        int[] tem = new int[r - l + 1];
        int i = 0;
        int s1 = l;
        int s2 = mid + 1;
        while (s1 <= mid && s2 <= r){
            tem[i++] = arr[s1] <= arr[s2] ? arr[s1++] : arr[s2++];
        }
        while (s1 <= mid){
            tem[i++] = arr[s1++];
        }
        while (s2 <= r) {
            tem[i++] = arr[s2++];
        }
        System.arraycopy(tem, 0, arr, l, r - l + 1);
    }

    /**
     * 快排
     * 荷兰国旗问题
     * 1.随机找出一个基数与最后一个元素交换（使用随机数命中的概率更优）
     * 2.找相等区域的左边界与右边界
     * 3.根据边界将左、右区域的元素排序
     */
    public static void fastSort(int[] arr, int l,int r) {
        if (isEmpty(arr)){
            return;
        }
        if (l < r){
            ArraysUtil.swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            fastSort(arr, l, p[0] - 1);
            fastSort(arr, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        //less区域置最左边
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                //把当前数归到less区域，下标+1
                ArraysUtil.swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                //把当前数归到more区域，下标-1
                ArraysUtil.swap(arr, --more, l);
            } else {
                //推着equals区域右移
                l++;
            }
        }
        //把num放到equal区域
        ArraysUtil.swap(arr, more, r);
        //返回less区域和equal区域的边界，equal区域和more区域的边界
        return new int[] { less + 1, more };
    }

    public static boolean isEmpty(int[] list){
        return Objects.isNull(list) || list.length < 2;
    }

    public static void main(String[] args) {
        int[] integers = {8, 3, 2, 1, 4, 6, 4, 7};
        //String[] methods = {"bubbleSort","hillSort","mergeSort","insertionSort","selectionSort","compore"};
        //for (int i = 0; i < methods.length; i++) {
        //    Class<?> clazz = ReflectionUtil.getClazz("com.dev.tools.sort.Example1");
        //    long begin = System.nanoTime();
        //    if (i == 2){
        //        Object test1 = ReflectionUtil.invokeMethod(ReflectionUtil.getMethod(clazz, methods[i], int[].class, int.class, int.class), ReflectionUtil.newInstance(clazz), integers, 0, integers.length - 1);
        //    }else{
        //        Object test1 = ReflectionUtil.invokeMethod(ReflectionUtil.getMethod(clazz, methods[i], int[].class), ReflectionUtil.newInstance(clazz), integers);
        //    }
        //    long end = System.nanoTime();
        //    System.out.println(Arrays.toString(integers));
        //    System.out.println(methods[i] + ":共耗时:" + (end - begin) + "ns");
        //}
        long begin = System.nanoTime();
        insertionSort(integers);
        long end = System.nanoTime();
        System.out.println("共耗时:" + (end - begin) + "ns");
        System.out.println(Arrays.toString(integers));
//        quickSort(integers,1,5);

    }
}
